import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by IntelliJ
 * Author:熊磊
 */
public class PolandNotation {
    public static void main(String[] args) {
        //定义一个逆波兰表达式
        //(3+4)*5-6
        //String suffixExpression = "3 4 + 5 * 6 -";
        //System.out.println(calculate(getListString(suffixExpression)));
        String a="1+((2+3)*4)-5";
        List<String> infix = toInfixExpressionList(a);
        System.out.println(infix);
        List<String> suffix = parseSuffixExpressionList(infix);
        System.out.println(suffix);


    }
    //后缀表达式转List
    public static List<String> getListString(String suffixExpression){
        String[] s = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String s1 : s) {
            list.add(s1);
        }
        return list;
    }
    //将中缀表达式转换成list
    public static List<String> toInfixExpressionList(String expresstion){
        List<String> list = new ArrayList<>();
        int i=0;
        String str="";
        char c;
        do{
           if ((c=expresstion.charAt(i))<48||(c>57)){
               list.add(c+"");
               i++;
           } else {
               while (i<expresstion.length()&&(c=expresstion.charAt(i))>=48 &&(c=expresstion.charAt(i))<=57){
                   str+=c;
                   i++;
               }
               list.add(str);
               str="";
           }
        }while (i<expresstion.length());
        return list;
    }
    //1 +((2+3)*4)-5  ==>1 23+ 4*+5-
    public static List<String> parseSuffixExpressionList(List<String> list){
        Stack<String> stack = new Stack<>();
        ArrayList<String> suffixList = new ArrayList<>();
        for (String item : list) {
            //如果是一个数就加入数组
            if (item.matches("\\d+")){
                suffixList.add(item);
            } else if (item.equals("(")){
                stack.push(item);
            } else if (item.equals(")")){
                while (!stack.peek().equals("(")){
                    suffixList.add(stack.pop());
                }
                stack.pop();  //将括号弹出
            } else {
                //当item的优先级小于等于栈顶的优先级时
                //先将左边的运算符加入数组中，否者会产生运算问题
                while (stack.size()!=0&&(getOperSize(item)<=getOperSize(stack.peek()))){
                    suffixList.add(stack.pop());
                }
                stack.push(item);
            }
        }
        //将栈内剩余的操作符加入数组中
        while (stack.size()!=0){
            suffixList.add(stack.pop());
        }

        return suffixList;
    }


    //获取运算符的优先级
    public static int getOperSize(String oper){
        switch (oper){
            case "+":
                return 1;
            case "-":
                return 1;
            case "*":
                return 2;
            case "/":
                return 2;
            case "(":
                return 0;
            default:
                System.out.println("运算符有误!!");
                return -1;
        }
    }


    //通过后缀数组计算出结果
    public static int calculate(List<String> list){
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            if (item.matches("\\d+")){ //匹配的是多位数
                stack.push(item);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res=0;
                if (item.equals("+")){
                    res= num1+num2;
                }else if (item.equals("-")){
                    res =num1 -num2;
                }else if (item.equals("*")){
                    res =num1*num2;
                }else if (item.equals("/")){
                    res =num1 /num2;
                }else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push(res+"");
            }
        }
        return Integer.parseInt(stack.pop());
    }
}
